package LeetCodeQuestionBank;

/**
 * 557. 反转字符串中的单词 III
 * 给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "Let's take LeetCode contest"
 * 输出："s'teL ekat edoCteeL tsetnoc"
 * 示例 2:
 *
 * 输入： s = "God Ding"
 * 输出："doG gniD"
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 5 * 10^4
 * s 包含可打印的 ASCII 字符。
 * s 不包含任何开头或结尾空格。
 * s 里 至少 有一个词。
 * s 中的所有单词都用一个空格隔开。
 */
public class T557 {

    /**
     * 两种思路
     * 1 使用split方法 分割 成字符串数组 逐个翻转 然后拼接 比较耗费内存
     * 2 在原地进行翻转 转化为 字符数组 同样是使用 双指针 进行局部翻转
     * 这里使用方法二
     */
    public String reverseWords(String s) {

        //转化为字符数组
        char[] chars = s.toCharArray();

        //遍历字符数组 利用空格 找到一个单词的开始 和结束坐标
        int start = 0;
        int end;

        for (int i = 0; i < chars.length; i++) {
            //遇到了空格 开始翻转前一个单词
            if (chars[i] == ' ') {
                end = i - 1;
                reversePort(chars, start, end);
                //下一个单词开始的位置
                start = i + 1;
            }

        }

        //还有最后一个单词没有翻转 因为最后一个字符不会是空格
        reversePort(chars, start, chars.length - 1);

        return String.copyValueOf(chars);

    }

    /**
     * 实现 字符数组 局部位置的翻转
     *
     * @param chars 字符数组的引用
     * @param start 开始index
     * @param end   结束index
     */
    public void reversePort(char[] chars, int start, int end) {

        char temp;

        while (start < end) {

            temp = chars[start];
            chars[start] = chars[end];
            chars[end] = temp;

            start++;
            end--;
        }

    }


    public static void main(String[] args) {
        T557 t557 = new T557();
        String s = t557.reverseWords("Let's take LeetCode contest");
        System.out.println(s);
    }

}
